#include <bits/stdc++.h>
using namespace std;
int partition(vector<int>& data,int start,int end,int length)
{
    int index = rand()%(end-start)+start;
    int small = start-1;
    swap(data[index],data[end]);
    for(int index = start;index<end;index++)
    {
        if(data[index]<data[end]) {
            small++;
            if(small != index)
                swap(data[index],data[small]);
        }
    }
    small++;
    swap(data[small],data[end]);
    return small;

}
void GetLeastNumber(vector<int>& input,int n,vector<int>& output,int k)
{
    if(k>n||n<=0||k<=0)
        return;
    int start=0,end=n-1;
    int index = partition(input,start,end,n);
    while (index!=k-1)
    {
        if(index>k-1)
        {
            end = index-1;
            index = partition(input,start,end,n);
        }
        else{
            start = index+1;
            index = partition(input,start,end,n);
        }
    }
    for(int i=0;i<k;i++)
        output[i] = input[i];
}
int main() {
    vector<int>a = {1,3,9,5,6,7};
    vector<int>b(a.size(),0);
    GetLeastNumber(a,6,b,3);
    for(int i=0;i<3;i++)
        cout<<b[i]<<" ";
    return 0;
}